#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <set>
#include <iomanip>
using namespace std;
// LL(1)文法
#define maxNum 100

class stack
{
public:
    vector<string> content;
    int top;
    stack()
    {
        top = 0;
    }
};

int findA(string &s, stack &a) // 在栈中查询String串的位置
{
    for (int i = 0; i < a.top; i++)
        if (s == a.content[i])
        {
            return i;
            break;
        }
    return -1;
}

int findAx(string &s, stack &a) // 在栈中查询String串中某一个字符的位置
{
    for (int i = 0; i < a.top; i++)
        if (a.content[i].find(s) >= 0 && a.content[i].find(s) < a.content[i].length())
        {
            return i;
            break;
        }
    return -1;
}

void VnToVtFunc(stack &one, stack two[])
{
    // 1.循环替换非终结符
    for (int i = 0; i < one.top; i++)
    {
        for (int j = 0; j < int(two[i].content.size()); j++)
        {
            // 如果相等 则为Vn
            while (findA(two[i].content[j], one) != -1)
            {
                // 在产生式左部寻找右部出现的Vn
                int poi = findA(two[i].content[j], one);
                vector<string>::iterator it = two[i].content.begin();
                while (it != two[i].content.end())
                {
                    if (*it == two[i].content[j])
                        it = two[i].content.erase(it);
                    else
                        it++;
                }
                // 在左部找到的Vn用FIRST集合替换
                for (int k = 0; k < (int)two[poi].content.size(); k++)
                    two[i].content.push_back(two[poi].content[k]);
            }
        }
    }
}

void first(stack &one, stack two[])
{
    // 1.提取首字母
    for (int i = 0; i < one.top; i++)
    {
        for (int j = 0; j < (int)two[i].content.size(); j++)
        {
            if (two[i].content[j] != "null")
                two[i].content[j] = two[i].content[j].substr(0, 1);
        }
    }
    // 2.进行循环替换
    VnToVtFunc(one, two);
}

// 对上下文无关文法进行分析 并计算FIRST集合
void First(vector<string> LawLL1, stack &one, stack two[])
{
    // 1. 分割分析文法 得到文法左右侧的信息
    vector<string> test;
    for (int index = 0; index < (int)LawLL1.size(); index++)
    {
        one.content.push_back(LawLL1[index].substr(0, LawLL1[index].find("->", 0)));
        one.top++;
        test.push_back(LawLL1[index].substr(LawLL1[index].find("->", 0) + 2));
        int tmp = 0;
        while (tmp <= (int)test[index].length() - 1)
        {
            if (test[index].find('|', tmp) >= 0 && test[index].find("|", tmp) < test[index].length())
                two[index].content.push_back(test[index].substr(tmp, test[index].find('|', tmp)));
            else
            {
                two[index].content.push_back(test[index].substr(tmp));
                break;
            }
            tmp = test[index].find('|', tmp) + 1;
        }
    }
    // 2. 调用first函数求first集合
    first(one, two);
    cout << "----------------------------------" << endl;
    cout << "该文法的FIRST集合:" << endl;
    // 3. 输出信息
    for (int i = 0; i < one.top; i++)
    {
        cout << "FIRST(" << one.content[i] << ") = {";
        for (int j = 0; j < (int)two[i].content.size(); j++)
            if (j == 0)
                cout << two[i].content[j];
            else
                cout << "," << two[i].content[j];
        cout << "}" << endl;
    }
    cout << "----------------------------------" << endl;
}

// 计算follow集合
void Follow(vector<string> LawLL1, stack &follow1, stack follow2[], stack first1, stack first2[])
{
    stack Vt, tmp[maxNum];
    for (int i = 0; i < first1.top; i++)
    {
        for (int j = 0; j < (int)first2[i].content.size(); j++)
        {
            // 1.将产生式FIRST集合中有空的存入Vt中
            if (first2[i].content[j] == "null")
            {
                Vt.content.push_back(first1.content[i]);
                Vt.top++;
                i++;
                j = 0;
            }
        }
    }

    // 2.分割分析文法
    vector<string> test;
    for (int i = 0; i < (int)LawLL1.size(); i++)
    {
        follow1.content.push_back(LawLL1[i].substr(0, LawLL1[i].find("->", 0)));
        follow1.top++;
        test.push_back(LawLL1[i].substr(LawLL1[i].find("->", 0) + 2));

        int tt = 0;
        while (tt <= (int)test[i].length() - 1)
        {
            if (test[i].find('|', tt) >= 0 && test[i].find("|", tt) < test[i].length())
                tmp[i].content.push_back(test[i].substr(tt, test[i].find('|', tt)));

            else
            {
                tmp[i].content.push_back(test[i].substr(tt));
                break;
            }
            tt = test[i].find('|', tt) + 1;
        }
    }

    // 求follow集合
    follow2[0].content.push_back("#");
    for (int k = 0; k < follow1.top; k++)
    {
        for (int i = 0; i < follow1.top; i++)
            for (int j = 0; j < (int)tmp[i].content.size(); j++)
            {
                // 3.如果某个产生式右部出现了非终结符
                if (tmp[i].content[j].find(follow1.content[k], 0) > 0 && tmp[i].content[j].find(follow1.content[k], 0) < tmp[i].content[j].length())
                {
                    string s = tmp[i].content[j];
                    // 截取非终结符后一个字符
                    string s1 = s.substr(s.find(follow1.content[k], 0) + 1);
                    // 无后一个字符 为αB型
                    if (s.find(follow1.content[k], 0) + 1 == s.length() && i != k)
                    {
                        for (int u = 0; u < (int)follow2[i].content.size(); u++)
                            if (follow2[i].content[u].length() > 0)
                                follow2[k].content.push_back(follow2[i].content[u]);
                    }
                    // 空字符
                    else if (s1.length() == 0)
                    {
                    }
                    // αBβ型
                    else
                    {
                        // β的第一个字符
                        string s2 = s1.substr(0, 1);
                        if ((findA(s2, follow1) != -1))
                            follow2[k].content.push_back(s1);
                        else
                            follow2[k].content.push_back(s1.substr(0, 1));
                        // 替换非终结符，并且去除了FIrst集中的空字符
                        for (int i = 0; i < follow1.top; i++)
                            for (int j = 0; j < (int)follow2[i].content.size(); j++)
                            {
                                while (findA(follow2[i].content[j], follow1) != -1)
                                {
                                    int poi = findA(follow2[i].content[j], follow1);
                                    vector<string>::iterator it = follow2[i].content.begin();
                                    while (it != follow2[i].content.end())
                                    {
                                        if (*it == follow2[i].content[j])
                                            it = follow2[i].content.erase(it);
                                        else
                                            it++;
                                    }
                                    for (int k = 0; k < (int)first2[poi].content.size(); k++)
                                        if (first2[poi].content[k] != "null")
                                            follow2[i].content.push_back(first2[poi].content[k]);
                                }
                            }
                        if (findAx(s1, Vt) != -1) // β可以推出空字符串
                        {
                            follow2[k].content.push_back(follow1.content[i]);
                            VnToVtFunc(follow1, follow2);
                        }
                    }
                }
            }
    }
    cout << "该文法的FOLLOW集合:" << endl;
    // 4.输出follow集合
    for (int i = 0; i < follow1.top; i++)
    {
        cout << "FOLLOW(" << follow1.content[i] << ") = {";
        for (int j = 0; j < (int)follow2[i].content.size(); j++)
            if (j == 0)
                cout << follow2[i].content[j];
            else
                cout << "," << follow2[i].content[j];
        cout << "}" << endl;
    }
    cout << "----------------------------------" << endl;
}
// 计算select集
void Select(vector<string> LawLL1, stack first[], stack follow[], stack &cst, stack dst[maxNum])
{
    stack one, two[maxNum];
    vector<string> test;
    // 1.分割文法的两侧获取信息
    for (int i = 0; i < (int)LawLL1.size(); i++)
    {
        one.content.push_back(LawLL1[i].substr(0, LawLL1[i].find("->", 0)));
        one.top++;
        test.push_back(LawLL1[i].substr(LawLL1[i].find("->", 0) + 2));
        int tt = 0;
        while (tt <= (int)test[i].length() - 1)
        {
            if (test[i].find('|', tt) >= 0 && test[i].find("|", tt) < test[i].length())
                two[i].content.push_back(test[i].substr(tt, test[i].find('|', tt)));
            else
            {
                two[i].content.push_back(test[i].substr(tt));
                break;
            }
            tt = test[i].find('|', tt) + 1;
        }
    }

    for (int i = 0; i < one.top; i++)
    {
        for (int j = 0; j < (int)two[i].content.size(); j++)
        {
            // 2.遍历将产生式写入
            cst.content.push_back(one.content[i] + "->" + two[i].content[j]);
            // 3.将推出为空的直接加到左部follow集
            if (two[i].content[j] == "null")
            {
                for (int k = 0; k < (int)follow[i].content.size(); k++)
                    dst[cst.top].content.push_back(follow[i].content[k]);
            }
            else
            {
                string str = two[i].content[j].substr(0, 1);

                if (findA(str, one) != -1)
                    dst[cst.top].content.push_back(str);

                else
                    dst[cst.top].content.push_back(str);
            }
            cst.top++;
        }
    }
    // 把select集中的所有非终结符实例删除掉
    // 注意要把Vn的first集中所有元素添加至select集
    for (int i = 0; i < cst.top; i++)
    {
        for (int j = 0; j < (int)dst[i].content.size(); j++)
        {
            while (findA(dst[i].content[j], one) != -1)
            {
                int pos = findA(dst[i].content[j], one);
                vector<string>::iterator it = dst[i].content.begin();
                while (it != dst[i].content.end())
                {
                    if (*it == dst[i].content[j])
                        it = dst[i].content.erase(it);

                    else
                        it++;
                }

                for (int k = 0; k < (int)first[pos].content.size(); k++)
                    if (first[pos].content[k] != "null")
                        dst[i].content.push_back(first[pos].content[k]);
            }
        }
    }
    // 输出SELECT集合
    cout << "该文法的SELECT集合:" << endl;
    for (int i = 0; i < cst.top; i++)
    {
        cout << "SELECT(" << cst.content[i] << ") = {";
        for (int j = 0; j < (int)dst[i].content.size(); j++)
            if (j == 0)
                cout << dst[i].content[j];
            else
                cout << "," << dst[i].content[j];
        cout << "}" << endl;
    }
    cout << "----------------------------------" << endl;
}

void Table(stack &selectA, stack selectB[], stack &firstA, vector<string> LawLL1, string table[][maxNum], int &width, int &length)
{
    stack sta, stb[maxNum];
    vector<string> vstmp;
    for (int i = 0; i < (int)LawLL1.size(); i++)
    {
        sta.content.push_back(LawLL1[i].substr(0, LawLL1[i].find("->", 0)));
        sta.top++;
        vstmp.push_back(LawLL1[i].substr(LawLL1[i].find("->", 0) + 2));
        int xx = 0;
        while (xx <= (int)vstmp[i].length() - 1)
        {
            if (vstmp[i].find('|', xx) >= 0 && vstmp[i].find("|", xx) < vstmp[i].length())
                stb[i].content.push_back(vstmp[i].substr(xx, vstmp[i].find('|', xx)));

            else
            {
                stb[i].content.push_back(vstmp[i].substr(xx));
                break;
            }
            xx = vstmp[i].find('|', xx) + 1;
        }
    }
    set<string> setVt;
    vector<string> vsSet;
    cout << "预测分析表:" << endl;
    for (int i = 0; i < selectA.top; i++)
        for (int j = 0; j < (int)selectB[i].content.size(); j++)
            vsSet.push_back(selectB[i].content[j]);

    setVt.insert(vsSet.begin(), vsSet.end());
    vsSet.assign(setVt.begin(), setVt.end());
    for (int i = 0; i < (int)vsSet.size(); i++)
        table[0][i + 1] = vsSet[i]; // 产生式右部放在第一行
    width = vsSet.size();
    for (int i = 0; i < firstA.top; i++)
        table[i + 1][0] = firstA.content[i]; // 产生式左部放在第一列
    length = firstA.top;
    for (int i = 0; i < selectA.top; i++)
        for (int j = 0; j < (int)selectB[i].content.size(); j++)
        {
            for (int u = 0; u < width; u++)
            {
                if (selectB[i].content[j] == table[0][u + 1])
                {

                    for (int k = 0; k < length; k++)
                        if (table[k + 1][0] == selectA.content[i].substr(0, 1))
                        {
                            table[k + 1][u + 1] = selectA.content[i].substr(3);
                            break;
                        }
                    break;
                }
            }
        } // 填表
    for (int i = 0; i <= length; i++)
    {
        for (int j = 0; j <= width; j++)
            cout << table[i][j] << '\t';
        cout << endl;
    }
    cout << "----------------------------------" << endl;
}
void ana(string table[][maxNum], int width, int length)
{
    vector<string> s, t;
    s.push_back("#");
    s.push_back("E"); // 分析栈初始化
    cout << "请输入以#结尾的要分析的句子：";
    string tt;
    cin >> tt;
    for (int i = tt.length() - 1; i >= 0; i--)
    {
        t.push_back(tt.substr(i, 1));
    }
    cout << setw(20) << setfill(' ') << left << "步骤"; // 头部

    cout << setw(20) << setfill(' ') << left << "对应串";

    cout << setw(20) << setfill(' ') << left << "输入串" << endl;

    int i = -1;
    while (t.size() >= 1)
    {
        i++;
        cout << setw(20) << setfill(' ') << left << i + 1;

        for (int i = 0; i < (int)s.size(); i++)
        {
            cout << s[i];
        }
        cout << setw(20) << setfill(' ') << left << " "; // 输出当前分析栈和剩余输入串
        for (int i = 0; i < (int)t.size(); i++)
        {
            cout << t[i];
        }
        cout << setw(20) << setfill(' ') << left << " ";
        cout << endl;
        if (t.size() == 1 && s.size() == 1)
        {
            cout << "接受" << endl;
            break;
        }

        if (s[s.size() - 1] == t[t.size() - 1]) // 终结符相等，出栈
        {

            s.pop_back();
            t.pop_back();
            i++;
            cout << setw(20) << setfill(' ') << left << i + 1;

            for (int i = 0; i < (int)s.size(); i++)
            {
                cout << s[i];
            }
            cout << setw(20) << setfill(' ') << left << " ";

            for (int i = 0; i < (int)t.size(); i++)
            {
                cout << t[i];
            }
            cout << setw(20) << setfill(' ') << left << " ";
            cout << endl;
        }

        int flag = 0;
        for (int i = 0; i < length; i++)
            if (table[i + 1][0] == s[s.size() - 1]) // 分析栈顶为非终结符
            {
                for (int j = 0; j < width; j++)
                    if (table[0][j + 1] == t[t.size() - 1])
                    {
                        if (table[i + 1][j + 1] == "null") // 预测分析表为空串
                        {
                            flag = 1;
                            s.pop_back();
                            break;
                        }
                        if (table[i + 1][j + 1].length() == 0) // 错误
                        {
                            flag = 2;
                            break;
                        }
                        for (int u = table[i + 1][j + 1].length() - 1; u >= 0; u--) // 非终结符的替换
                        {
                            if (u == (int)table[i + 1][j + 1].length() - 1)
                                s[s.size() - 1] = table[i + 1][j + 1].substr(u, 1);
                            else
                            {
                                if (u >= 0)
                                    s.push_back(table[i + 1][j + 1].substr(u, 1));
                            }
                        }
                        flag = 1;
                        if (flag == 1)
                            break;
                    }
                if (flag == 1)
                    break;
            }
        if (flag == 2)
        {
            cout << "拒绝" << endl;
            break;
        }
    }
}
int main()
{
    vector<string> rule;
    vector<string> rule_LL1;
    int a;
    string s;
    cout << "请输入产生式数量" << endl;
    cin >> a;
    for (int aa = 0; aa < a; aa++)
    {
        cout << "请输入第" << aa + 1 << "个产生式：";
        cin >> s;
        rule_LL1.push_back(s);
    }

    stack firstA, firstB[maxNum], followA, followB[maxNum], selectA, selectB[maxNum];
    string table[maxNum][maxNum];
    int width = 0, length = 0;
    for (int i = 0; i < (int)rule_LL1.size(); i++)
    {
        cout << rule_LL1[i] << endl;
    }
    cout << "以上文法长度" << rule_LL1.size() << "行" << endl;
    First(rule_LL1, firstA, firstB);
    Follow(rule_LL1, followA, followB, firstA, firstB);
    Select(rule_LL1, firstB, followB, selectA, selectB);
    Table(selectA, selectB, firstA, rule_LL1, table, width, length);
    ana(table, width, length);
}